|
In combinatorics, Bertrand's ballot problem is the question: "In an election where candidate A receives ''p'' votes and candidate B receives ''q'' votes with ''p'' > ''q'', what is the probability that A will be strictly ahead of B throughout the count?" The answer is : The result was first published by W. A. Whitworth in 1878, but is named after Joseph Louis François Bertrand who rediscovered it in 1887.〔.〕〔J. Bertrand, Solution d'un problème, Comptes Rendus de l'Académie des Sciences, Paris 105 (1887), 369.〕 In Bertrand's original paper, he sketches a proof based on a general formula for the number of favourable sequences using a recursion relation. He remarks that it seems probable that such a simple result could be proved by a more direct method. Such a proof was given by Désiré André,〔D. André, Solution directe du problème résolu par M. Bertrand, Comptes Rendus de l’Académie des Sciences, Paris 105 (1887) 436–437.〕 based on the observation that the unfavourable sequences can be divided into two equally probable cases, one of which (the case where B receives the first vote) is easily computed; he proves the equality by an explicit bijection. A variation of his method is popularly known as André's reflection method, although André did not use any reflections.〔(Renault, Marc, Lost (and found) in translation: André's actual method and its application to the generalized ballot problem. Amer. Math. Monthly 115 (2008), no. 4, 358--363. )〕 ==Example== Suppose there are 5 voters, of whom 3 vote for candidate ''A'' and 2 vote for candidate ''B'' (so ''p'' = 3 and ''q'' = 2). There are ten possibilities for the order of the votes cast: *''AAABB'' *''AABAB'' *''ABAAB'' *''BAAAB'' *''AABBA'' *''ABABA'' *''BAABA'' *''ABBAA'' *''BABAA'' *''BBAAA'' For the order ''AABAB'', the tally of the votes as the election progresses is: For each column the tally for ''A'' is always larger than the tally for ''B'' so the ''A'' is always strictly ahead of ''B''. For the order ''AABBA'' the tally of the votes as the election progresses is: For this order, ''B'' is tied with ''A'' after the fourth vote, so ''A'' is not always strictly ahead of ''B''. Of the 10 possible orders, ''A'' is always ahead of ''B'' only for ''AAABB'' and ''AABAB''. So the probability that ''A'' will always be strictly ahead is : and this is indeed equal to as the theorem predicts. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bertrand's ballot theorem」の詳細全文を読む スポンサード リンク
|